#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 093. 复原 IP 地址.py
@time: 2022/1/19 22:14
@desc: https://leetcode-cn.com/problems/restore-ip-addresses/
> 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

1. dfs
2. Ot(3^SET_COUNT*|s|), Os(SET_COUNT), Ot(|s|), Os(1)?

'''


class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        SEG_COUNT = 4
        # 结果
        ans = []
        # ip每段所组成的列表
        segments = [0] * SEG_COUNT

        # dfs
        def dfs(seg_id, seg_start):
            """
            :type seg_id: int 当前dfs到第几段
            :type seg_start: int 当前dfs到字符串的哪一位
            """
            # 退出条件1：前4位都已经有元素了
            if seg_id == SEG_COUNT:
                # 如果正好到了字符串末尾，就说明合法
                if seg_start == len(s):
                    ip_addr = '.'.join([str(seg) for seg in segments])
                    ans.append(ip_addr)
                return

            # 退出条件2：没有安排完每一段就到了字符串末尾，就退出
            if seg_start == len(s):
                return

            # 当遍历到0，那只能作为单独的数字作为ip中的其中一段
            if s[seg_start] == '0':
                segments[seg_id] = 0
                dfs(seg_id + 1, seg_start + 1)

            addr = 0
            # 遍历每种尾部情况
            for seg_end in range(seg_start, len(s)):
                addr = addr * 10 + int(s[seg_end])
                # 检查合法性
                if 0 < addr <= 255:
                    # 合法就加入，并检查下一种可能
                    segments[seg_id] = addr
                    dfs(seg_id + 1, seg_end + 1)
                else:
                    # 剪枝：当前数值都已经超了，再加一位更超
                    break

        dfs(0, 0)
        return ans